#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ARRAY_LEN 100  // 输入数组最大长度
#define MAX_RESULT_CNT 161700  // 最大组合数（100选3=161700，按需调整）

// 单个组合（存储3个元素）
typedef struct {
    int elements[3];  // 组合元素（固定长度3，与Python select_3对应）
} Combination;

// 结果集（存储所有组合）
typedef struct {
    Combination* items;  // 组合数组
    int count;           // 已存储组合数
} ResultSet;

/**
 * 初始化结果集
 * @return: 初始化后的结果集（需调用者释放）
 */
ResultSet* result_set_init() {
    ResultSet* rs = (ResultSet*)malloc(sizeof(ResultSet));
    rs->items = (Combination*)malloc(MAX_RESULT_CNT * sizeof(Combination));
    rs->count = 0;
    return rs;
}

/**
 * 向结果集添加一个组合
 * @param rs: 结果集
 * @param a, b, c: 组合的三个元素（按字典序顺序）
 */
void result_set_add(ResultSet* rs, int a, int b, int c) {
    if (rs->count >= MAX_RESULT_CNT) {
        fprintf(stderr, "结果集溢出！请增大MAX_RESULT_CNT\n");
        return;
    }
    Combination* comb = &rs->items[rs->count++];
    comb->elements[0] = a;
    comb->elements[1] = b;
    comb->elements[2] = c;
}

/**
 * 字典序法选择3个元素（对应Python select_3函数）
 * @param arr: 输入数组（int类型）
 * @param arr_len: 输入数组长度
 * @return: 结果集（需调用者释放）
 */
ResultSet* select_3(const int arr[], int arr_len) {
    if (arr_len < 3) {
        fprintf(stderr, "数组长度必须≥3才能选择3个元素！\n");
        return NULL;
    }

    ResultSet* rs = result_set_init();

    // 三重循环：i < j < k，确保字典序且不重复（组合特性）
    for (int i = 0; i < arr_len; i++) {
        for (int j = i + 1; j < arr_len; j++) {
            for (int k = j + 1; k < arr_len; k++) {
                // 添加组合 [arr[i], arr[j], arr[k]]
                result_set_add(rs, arr[i], arr[j], arr[k]);
            }
        }
    }

    return rs;
}

/**
 * 打印结果集（模拟Python列表输出格式）
 * @param rs: 结果集
 */
void print_result(ResultSet* rs) {
    printf("[");
    for (int i = 0; i < rs->count; i++) {
        Combination* comb = &rs->items[i];
        printf("[%d, %d, %d]", comb->elements[0], comb->elements[1], comb->elements[2]);
        if (i != rs->count - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

/**
 * 释放结果集内存
 * @param rs: 结果集
 */
void result_set_free(ResultSet* rs) {
    free(rs->items);
    free(rs);
}

// 测试主函数（与Python测试用例一致）
int main() {
    // 测试数组：[1, 2, 3, 4, 5]
    int arr[] = {1, 2, 3, 4, 5};
    int arr_len = sizeof(arr) / sizeof(arr[0]);

    // 调用字典序选择3个元素
    ResultSet* rs = select_3(arr, arr_len);

    // 打印结果（与Python输出完全一致）
    printf("select_3([1, 2, 3, 4, 5]) = ");
    print_result(rs);

    // 释放内存
    result_set_free(rs);

    return 0;
}